APLS: Average Path Length Similarity
Nội dung
- 1. Giới thiệu về APLS
- 2. Mạng lưới đường bộ dưới dạng đồ thị (Road Network Graph)
- 3. Khó khăn trong đánh giá mô hình trích xuất mạng lưới đường bộ
- 4. APLS – Metric mới cho đánh giá mạng lưới đường bộ
- 5. Quy trình snapping node trong APLS
- 6. Tham khảo
1. Giới thiệu về APLS
APLS (Average Path Length Similarity) là một metric mới được phát triển nhằm đánh giá hiệu quả các mô hình trích xuất mạng lưới đường bộ, đặc biệt trong thử thách SpaceNet3. SpaceNet3 là một benchmark nổi bật trong lĩnh vực xử lý ảnh vệ tinh để trích xuất bản đồ đường bộ với dữ liệu lớn và đa dạng.
2. Mạng lưới đường bộ dưới dạng đồ thị (Road Network Graph)
Mạng lưới đường bộ có thể được biểu diễn dưới dạng đồ thị (graph), trong đó các nút (nodes) tương ứng với điểm giao nhau hoặc điểm đặc trưng trên đường, còn các cạnh (edges) là đoạn đường nối giữa các nút. Việc biểu diễn này cho phép xử lý các bài toán như tìm đường đi ngắn nhất, phân tích kết nối, hoặc mô phỏng giao thông.
Mô hình deep learning sẽ cố gắng "phân đoạn" các pixel road từ ảnh và đưa vào đồ thị đường
Đồ thị mạng lưới đường bộ gốc (Ground Truth Graph)
Minh họa tìm đường đi ngắn nhất sử dụng thuật toán Dijkstra
3. Khó khăn trong đánh giá mô hình trích xuất mạng lưới đường bộ
Đánh giá các mô hình trích xuất mạng lưới đường bộ truyền thống thường dựa trên chỉ số pixel (pixel-based metrics) như IoU hay pixel accuracy. Tuy nhiên, các metric này không phản ánh đầy đủ chất lượng cấu trúc mạng lưới, ví dụ như độ liên kết hay tính chính xác của các đoạn đường nối.
Điều này dẫn đến khó khăn trong việc đo lường chính xác khả năng mô hình tạo ra bản đồ đường bộ có tính ứng dụng thực tế cao.
4. APLS – Metric mới cho đánh giá mạng lưới đường bộ
APLS được thiết kế nhằm khắc phục những hạn chế của các metric truyền thống, vốn thường dựa trên đánh giá theo từng pixel mà bỏ qua tính chất cấu trúc của mạng lưới đường bộ. Thay vào đó, APLS so sánh sự tương đồng về các đường đi ngắn nhất giữa mạng lưới thật và mạng lưới dự đoán, từ đó đánh giá chất lượng mô hình trích xuất đường bộ một cách chính xác hơn.
Công thức đánh giá C đi đường APLS:
\[C = 1 - \frac{1}{N} \sum \min\left\{1, \frac{\left|L(a,b) - L(a', b')\right|}{L(a,b)}\right\}\]Trong đó:
- $ N $: Số lượng đường đi duy nhất.
- $ L(a,b) $: Độ dài đường đi giữa nút $a$ và $b$ trong đồ thị ground truth.
- $ L(a’, b’) $: Độ dài đường đi giữa các nút tương ứng $a’$ và $b’$ trong đồ thị dự đoán.
- Tổng được tính trên tất cả các cặp nút nguồn $a$ và đích $b$ trong đồ thị ground truth.
- $ a’, b’ $: Là các nút tương ứng sau khi snapping từ đồ thị ground truth sang đồ thị dự đoán.
Giá trị $C$ nằm trong khoảng từ 0 (tệ) đến 1 (hoàn hảo), phản ánh độ tương đồng về cấu trúc đường đi giữa hai đồ thị.
Nhận xét:
- APLS ưu tiên đánh giá cấu trúc mạng lưới, đặc biệt những đoạn đường quan trọng có tần suất sử dụng cao (liên quan đến betweenness centrality), giúp phát hiện các lỗi lớn như mất đoạn đường hoặc ngắt kết nối.
- Nếu đường đi ngắn nhất giữa hai nút trong đồ thị dự đoán không tồn tại (nghĩa là mất đoạn đường), mức phạt tối đa 1.0 sẽ được áp dụng, khiến điểm APLS giảm mạnh.
- Điều này giúp APLS phạt nặng những lỗi nghiêm trọng như mất đường hoặc đoạn đường không liền mạch, đảm bảo rằng các tuyến đường trong mạng dự đoán phải được kết nối chính xác.
- Việc tính toán gồm hai bước snapping ngược nhau giữa đồ thị thật và dự đoán giúp đánh giá toàn diện, tránh bỏ sót lỗi ở cả hai phía.
- Nhờ vậy, APLS được xem là một metric phù hợp và hiệu quả cho các bài toán trích xuất và đánh giá mạng lưới đường bộ từ ảnh vệ tinh hoặc dữ liệu địa lý phức tạp.
5. Quy trình snapping node trong APLS
B: Đồ thị được đề xuất.
C: Đồ thị chuẩn (màu cam) và các nút kiểm soát (màu đỏ) chồng lên đồ thị đề xuất (màu xám).
D: Như hình C, nhưng có thêm vùng đệm (buffer - màu vàng) xung quanh đồ thị đề xuất.
E: Các nút kiểm soát của đồ thị chuẩn được gắn vào cạnh gần nhất của đồ thị đề xuất, trừ các nút nằm ngoài vùng đệm (màu xám).
F: Đồ thị đề xuất cuối cùng với các nút đã được gắn đúng vị trí để so sánh với đồ thị A.
6. Cách APLS hoạt động và tham khảo
[1] SpaceNet3 Road Detection and Routing Challenge. 🔗 https://spacenet.ai/spacenet-challenge/overview/
[2] Road Network Extraction and Evaluation using APLS. 🔗 https://arxiv.org/abs/1906.03563